package com.example.tree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 请实现两个函数，分别用来序列化和反序列化二叉树。
 *  你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
 *  你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 *
 *  提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方
 * 法解决这个问题。
 *
 *  示例：
 * 输入：root = [1,2,3,null,null,4,5]
 * 输出：[1,2,3,null,null,4,5]
 *
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1]
 * 输出：[5,4,8,11,null,13,4,7,2,null,null,5,1]
 *            5
 *          /   \
 *         4     8
 *        /     / \
 *       11    13  4
 *      /  \      / \
 *     7    2    5   1
 */
public class Leetcode297_Offer37_CodeBinTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right = new TreeNode(8);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);

        Codec codec = new Codec();
        String res = codec.serialize(root);
        System.out.println(res);

        TreeNode newRoot = codec.deserialize(res);
        System.out.println(newRoot.val);
        System.out.println(newRoot.left.val);
        System.out.println(newRoot.left.left.val);
        System.out.println(newRoot.left.left.left.val);
        System.out.println(newRoot.left.right);
        System.out.println(newRoot.right.right.val);


    }

    /**
     * BFS方式
     */
    static class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder res = new StringBuilder();
            res.append("[");
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode tmp = queue.poll();
                if(tmp != null){ // 不用判断子树是否为空,直接将左右子树加入队列即可
                    res.append("" + tmp.val);
                    queue.offer(tmp.left);
                    queue.offer(tmp.right);
                }else{ // 当前节点是null,也需要拼接
                    res.append("null");
                }
                res.append(",");
            }

            res.replace(res.length() - 1, res.length(), "]");
            return res.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            data = data.substring(1, data.length() - 1);
            if ("null".equals(data)) return null;

            String[] nodeVals = data.split(",");
            TreeNode root = new TreeNode(Integer.parseInt(nodeVals[0]));
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int i = 1;
            while (!queue.isEmpty()) {
                TreeNode tmp = queue.poll();
                // 构造左子树
                if (!"null".equals(nodeVals[i])) {
                    tmp.left = new TreeNode(Integer.parseInt(nodeVals[i]));
                    queue.offer(tmp.left);
                }
                i++;

                // 构造右子树
                if (!"null".equals(nodeVals[i])) {
                    tmp.right = new TreeNode(Integer.parseInt(nodeVals[i]));
                    queue.offer(tmp.right);
                }
                i++;
            }
            return root;
        }
    }
}
